package sort;

import org.junit.Test;

import java.time.LocalDateTime;
import java.time.ZoneOffset;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.AbstractQueuedSynchronizer;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.LockSupport;
import java.util.concurrent.locks.ReentrantLock;
import java.util.stream.IntStream;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/29 20:26
 */
public class leetcode前k个高频元素 {

    /*
    这个 问题 就是 topK 问题
    甜咦的 知乎讲解！
    https://zhuanlan.zhihu.com/p/114699207

    ==
    这里 对使用 对数器的 一些 问题 解释,
    lc 数据 保证, 满足要求的 前 k 元素的 集合的唯一性
    但是 使用对数器 满足不了  这一点, 所以 使用对数器的 时候 可能会出现一些问题!
     */


    /*
      手写一个堆,建 堆的过程可以实现 O(N)
      但是总体的时间复杂度, 还是 O(N * lgK)
     */

    class Solution {
        /*
         通过下面的代码熟悉一下 ,stream 的用法!
         stream 还是很猛的! (只不过效率并不高!)
         */
        public int[] topKFrequent(int[] nums, int k) {
            Map<Integer, Integer> map = new HashMap<>();
            IntStream.of(nums).forEach(num -> map.put(num, map.getOrDefault(num,0) + 1));
            PriorityQueue<int[]> queue = new PriorityQueue<>(k, (p1, p2) -> p1[1] - p2[1]);
            map.forEach((key, value) -> {
                queue.add(new int[]{key, value});
                if (queue.size() > k) {
                    queue.poll();
                }
            });
            return queue.stream().mapToInt(x -> x[0]).toArray();
        }
    }



    /*
     快排的 思想 来做! (目前来说是最快!)
     时空复杂度都是 O(N)
     top k的快排解法!
     迭代 和 递归的写法 都写出来了!
     递归好像 还更快一些!
     */

    public int[] solutionFour(int nums[],int k){
        int ans[] = new int[k];
        Map<Integer,Integer> map  = new HashMap<>(nums.length);
        Arrays.stream(nums).forEach(x  -> map.put(x,map.getOrDefault(x,0) + 1));
        Integer[] integers = map.keySet().toArray(new Integer[0]);
        int l = 0, r = integers.length - 1 ,ansIndex = 0,len = integers.length;
        while(true){
            if(l == r){
                ansIndex = l;
                break;
            }
            int[] partition = partition(integers, l, r, map);
            if(len - k >= partition[0] && len - k <= partition[1]){
                ansIndex = len - k;
                break;
            }else if(len - k < partition[0]){
                r = partition[1] - 1;
            }else{
                l = partition[0] + 1;
            }
        }
//        ansIndex = process(integers,l,r,integers.length - k,map);
        int index = 0;
        for(int i = ansIndex;i < integers.length;i++){
            ans[index++] = integers[i];
        }

        return ans;
    }
    public int process(Integer arr[],int l,int r,int k,Map<Integer,Integer> map){
        if(l == r){
            return l;
        }
        int index = l + (int)(Math.random() * (r - l + 1));
        swap(arr,index,r);
        int[] partition = partition(arr, l, r, map);
        if(k >= partition[0] && k <= partition[1]){
            return k;
        }else if(k < partition[0]){
           return  process(arr,l,partition[0] - 1,k,map);
        }else{
            return process(arr,partition[1] + 1,r,k,map);
        }
    }

    public int[] partition(Integer arr[],int l,int r,Map<Integer,Integer> map){
        int less = l - 1,more = r,index = l;
        int piovt = map.get(arr[r]);
        while(index < more){
            int value = map.get(arr[index]);
            if(value == piovt){
                index++;
            }else if(value < piovt){
                swap(arr,++less,index++);
            }else{
                swap(arr,index,--more);
            }
        }
        swap(arr,more,r);
        return new int[]{less + 1,more};
    }
    @Test
    public void tes1t(){
        int nums[] =  {1,1,1,2,2,3};
//        System.out.println(Arrays.toString(Arrays.copyOfRange(nums,0,5)));
        System.out.println(Arrays.toString(solutionTwo(nums,2)));
        System.out.println(Arrays.toString(solutionThreeUpdate(nums,2)));
        System.out.println(Arrays.toString(solutionFour(nums,2)));





    }







    /*
    改进版本:
    但是 计数的本质,没变 (就是以 元素 出现的 次数, 作为下标进行计数 , 这个是 关键,也是一个 思维点!)

    =
    有点抽象,写出来就明白了; 数组的每一个元素 都是一个 都是一个 list,而 list 可以装多个值, 这不就解决了!
    List<Integer> [] count;
    == 时间复杂度 O(N) ,但是 空间复杂度有点抽象!
    A了
     */
    public int[] solutionThreeUpdate(int nums[],int k){
        Map<Integer,Integer> map = new HashMap<>(nums.length);

        for(int num : nums){
            map.put(num,map.getOrDefault(num,0) + 1);
        }
        List<Integer> count[] = new List[nums.length + 1];
//        List<Integer> count1[] = new ArrayList[nums.length + 1];
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            /*
            ***
             这里 还要注意 一下, 如果  count[i] != null ,说明已经创建过了, 那就不用再 new ,否则 会覆盖之前的记录
            *****
             */
            if(count[entry.getValue()] == null){
                count[entry.getValue()] = new ArrayList<>();
            }
            count[entry.getValue()].add(entry.getKey());
        }
        int ans[] = new int[k] ,index = 0;
        for(int i = count.length - 1;i >= 0;i--){
            if(index == k){
                break;
            }
            if(count[i] != null){
                for(int num : count[i]){
                    /*
                     为什么 不考虑 这个时候,ans 数组的大小超过 k ,因为 题目说明,保证 k个高频元素的集合是唯一的
                     所以, 这里面根本就不用 再 判断 index == k 的情况
                     */
                    ans[index++] = num;
                }
            }
        }
        return ans;
    }

    /*
     计数排序,来写,
     现在的 问题,在于,topk的集合当中, 如果有 出现相同次数的 元素, 就不对!
     nums = [1,2] , k = 2, 这样的 就不对!
     */
    public int[] solutionThree(int nums[],int k){
       /*
        题意已经暗含了, 在满足的结果集中,不会出现, 一些元素的 出现次数相同!
        */
        Map<Integer,Integer> map = new HashMap<>(nums.length);
        int count[] = new int[nums.length + 1];
        Arrays.fill(count,Integer.MIN_VALUE);
        for(int num : nums){
            map.put(num,map.getOrDefault(num,0) + 1);
        }
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            count[entry.getValue()] = entry.getKey();
        }
        int ans[] = new int[k] ,index = 0;
        for(int i = count.length - 1;i >= 0;i--){
            if(index == k){
                break;
            }
            if(count[i] != Integer.MIN_VALUE){
                ans[index++] = count[i];
            }
        }
        return ans;
    }










    /*
     时间复杂度 O(K * N)
     空间复杂度 O(1)
     选择排序 &  冒泡排序 都可以做到!
     但是 插入 排序好像不行!
     */

    public int[] solutionTwo(int nums[],int k){
        Map<Integer,Integer> map = new HashMap<>(nums.length);
        for(int num : nums){
            map.put(num,map.getOrDefault(num,0) + 1);
        }
        Integer[] integers = map.keySet().toArray(new Integer[0]);
        for(int i = 0;i < k;i++){
            int maxIndex = i,max = map.get(integers[i]);
            /*
             下面使用 冒泡排序 道理一样的
             */
            for(int j = i;j < integers.length;j++){
                if(map.get(integers[j]) > max){
                    maxIndex = j;
                    max = map.get(integers[j]);
                }
            }
            swap(integers,i,maxIndex);
        }
        int ans[] = new int[k];
        for(int i = 0;i < k;i++){
            ans[i] = integers[i];
        }
        return ans;
//        return  Arrays.copyOfRange(integers,0,k);
    }

    private void swap(Integer[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }








    /*
    虽然 a 了
    但是 实践复杂度是 O（N * lgK）
    空间复杂度O（N）
    这个 题 把 k的大小设置为 k + 1 还是有 很大的好处的（相当于有一个 哨兵的 位置）！这一点还是很妙的
     */
    public int[] solution(int nums[], int k) {
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        Queue<Integer> queue  = new PriorityQueue<>(k + 1,(a , b) -> map.get(a) -  map.get(b));
        int ans[] = new int[k];
        // 统计
        for(int num : nums){
            map.put(num,map.getOrDefault(num,0) + 1);
        }
        // 下面是放入 小根堆
        for(int num :map.keySet()){
            queue.add(num);
            if(queue.size() == k + 1){
                queue.poll();
            }
        }
//        System.out.println(queue);
        int index = 0;
        for(int num : queue){
            ans[index++] = num;
//            System.out.println(num);
        }
        return ans;
    }


    /*
     跟上面的一样，但是 是，另外一种写法！
     O（N * lgK）
     ：
     区别主要在于， 维护的 对结构不太一样！

     ==
     我的 评价 是, 不如 上一个版本的 简洁, 直接 把 queue.size 设置为 k + 1, 多一个 位置 用来,做 判断的位置!
     */
     public int[] solutionOne(int nums[],int k){
//         Arrays.stream(nums).boxed().  这个 stream 流  怎么写！ boxed 包装一下，成为包装类
         Map<Integer,Integer> map = new HashMap<>(nums.length);
         Queue<Integer> queue = new PriorityQueue<>((a,b) -> map.get(a) - map.get(b));
         int ans [] = new int[k];
         for(int num : nums){
             map.put(num,map.getOrDefault(num,0) + 1);
         }

//         Object[] objects = map.keySet().stream().toArray();
         Integer[] integers = map.keySet().toArray(new Integer[0]);
         int i = 0;
            /*
             错误的 点， 就在 这里！
             queue 的size == k
             不能
             */
            for(;i < integers.length;i++){
                if(queue.size() < k){
                    queue.add(integers[i]);
                }
                /*
                 主要的 核心点， 在于 ，queue.size == k 的时候,不能直接放入,
                 而是要先判断一下, 再 做操作 才对!
                 */
                else if(map.get(queue.peek()) < map.get(integers[i])){
                    queue.poll();
                    queue.add(integers[i]);
                }
            }
         i = 0;
         for(int num : queue){
             ans[i++] = num;
         }
         return ans;
     }

     @Test
     public void testOne(){
         int nums[] = {1, 1, 1, 2, 2, 3}, k = 2;
         System.out.println(Arrays.toString(solutionOne(nums,k)));
     }





    /*
     题 不难， 怎么 找一种 合适的结构进行 存储？
     堆 结构 ！
     */
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new TreeMap<>((a, b) -> b - a);
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        int index = 0, ans[] = new int[k];
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (index == k) {
                break;
            }
            ans[index++] = entry.getKey();
        }
        System.out.println(map);


        return ans;
    }

    @Test
    public void test() {
        testRight();
    }



    public int[] ramdomArray(int arraySize, int max, int min, boolean fix) {
        int ramdomArraySize = fix ? arraySize : (int) (Math.random() * (arraySize + 1)); // 数组的长度 , 由fix 来控制 是否随机
        int arr[] = new int[ramdomArraySize];
        if (min == 0) {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max + 1)); // arr[i] = [0 , max]
            }
        } else if (min == 1) {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max)) + 1;//  arr[i] =  [1 , max + 1)
            }
        } else {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max + 1) - Math.random() * (max + 1)); // 可正 可 负 可为 0
            }
        }
        return arr;
    }


    public void testRight() {
        int testTimes = 10; // 自己写！
        int arraySize = 10;
        int max = 100;
        int min = -1;
        boolean fix = false;
        boolean isSuccess = true;
        for(int i = 0;i <  testTimes;i++){
            int[] ints = ramdomArray(arraySize, max, min, fix);
            int arr1[] = Arrays.copyOf(ints, ints.length);
            int arr2[] = Arrays.copyOf(ints, ints.length);
            // 你的方法
            int k = (int)(Math.random() * (arr1.length));
            int[] ints1 = solutionTwo(arr1, k);
            int[] ints2 = solutionThreeUpdate(arr2, k);
//            int[] ints2 = solution(arr2, k);
//            System.out.println(Arrays.toString(ints1));
//            System.out.println(Arrays.toString(ints2));
            Arrays.sort(ints1);
            Arrays.sort(ints2);
            if(!Arrays.equals(ints1,ints2)){
                 /*
                  说明 有问题， 可以打印下，数组，看下是什么 问题！
                  */
                isSuccess = false;
                System.out.println(Arrays.toString(ints1) + " ints1");
                System.out.println(Arrays.toString(ints2) + "ints2");
                System.out.println(Arrays.toString(ints) + "ints");
                System.out.println(k);
            }
        }
        System.out.println(isSuccess ? "success" : "fuck!");
    }



}
